Search results for "Chinese postman problem"

showing 3 items of 3 documents

The Chinese Postman Problem with Load-Dependent Costs

2018

[EN] We introduce an interesting variant of the well-known Chinese postman problem (CPP). While in the CPP the cost of traversing an edge is a constant (equal to its length), in the variant we present here the cost of traversing an edge depends on its length and on the weight of the vehicle at the moment it is traversed. This problem is inspired by the perspective of minimizing pollution in transportation, since the amount of pollution emitted by a vehicle not only depends on the travel distance but also on its load, among other factors. We define the problem, study its computational complexity, provide two mathematical programming formulations, and propose two metaheuristics for its soluti…

050210 logistics & transportationMathematical optimization021103 operations researchTraverse/dk/atira/pure/subjectarea/asjc/2200/2205Computational complexity theory05 social sciencesPerspective (graphical)0211 other engineering and technologiesArc-routing problemsTransportation02 engineering and technologyMoment (mathematics)Route inspection problemChinese postman problem/dk/atira/pure/subjectarea/asjc/3300/33130502 economics and businessPollution routingEnhanced Data Rates for GSM EvolutionConstant (mathematics)MATEMATICA APLICADAMetaheuristicCivil and Structural EngineeringMathematics
researchProduct

A comparison of two different formulations for Arc Routing Problems on Mixed graphs

2006

[EN] Arc routing problems on mixed graphs have been modelled in the literature either using just one variable per edge or associating to each edge two variables, each one representing its traversal in the corresponding direction. In this paper, and using the mixed general routing problem as an example, we compare theoretical and computationally both formulations as well as the lower bounds obtained from them using Linear Programming based methods. Extensive computational experiments, including some big and newly generated random instances, are presented.

Arc routingGeneral Computer ScienceLinear programmingMixed Chinese postman problemMixed graphMixed rural postman problemManagement Science and Operations ResearchRoute inspection problemTree traversalModeling and SimulationEnhanced Data Rates for GSM EvolutionRouting (electronic design automation)Mixed general routing problemMATEMATICA APLICADAAlgorithmArc routingMathematicsVariable (mathematics)
researchProduct

The mixed general routing polyhedron

2003

[EN] In Arc Routing Problems, ARPs, the aim is to find on a graph a minimum cost traversal satisfying some conditions related to the links of the graph. Due to restrictions to traverse some streets in a specified way, most applications of ARPs must be modeled with a mixed graph. Although several exact algorithms have been proposed, no polyhedral investigations have been done for ARPs on a mixed graph. In this paper we deal with the Mixed General Routing Problem which consists of finding a minimum cost traversal of a given link subset and a given vertex subset of a mixed graph. A formulation is given that uses only one variable for each link (edge or arc) of the graph. Some properties of the…

Discrete mathematicsGeneral MathematicsArc RoutingMixed graphFacetsPolyhedral combinatoricsRural Postman Problemlaw.inventionGeneral Routing ProblemCombinatoricsTree traversalMixed Chinese Postman ProblemlawroutingGraph traversalGraph (abstract data type)Destination-Sequenced Distance Vector routingMATEMATICA APLICADACircle graphArc routingSoftwareMathematicsofComputing_DISCRETEMATHEMATICSMathematicsPolyhedral graph
researchProduct